package com.atguigu.linklist;

public class FindTheCommonNode {
    public static ListNode findTheCommonNode(ListNode head1,ListNode head2){
        if(head1==null || head2==null) return null;
        int n=0;
        ListNode cur1=head1;
        while(cur1.next!=null){ //到最后一个节点
            n++;
            cur1=cur1.next;
        }
        ListNode cur2=head2;
        while(cur2.next!=null){
            n--;
            cur2=cur2.next;
        }
        if(cur1!=cur2){
            return null; //最后一个节点不相同，无相交
        }
        //n>0 说明 cur1比cur2长，n=0说明一样长，n<0说明cur2长
        ListNode fast=(n>0)?head1:head2;
        ListNode slow=null;
        if(fast==head1){
            slow=head2;
        }else{
            slow=head1;
            n=-n;
        }
        while(n>0){
            fast=fast.next;
        }
        while(fast!=slow){
            fast=fast.next;
            slow=slow.next;
        }
        return fast;
    }
}
